package my.util;

import java.util.function.Consumer;

/**
 * <p>
 * 动态数组
 * </p>
 *
 * @author AJun
 * @since 2020/8/17
 */
@SuppressWarnings("ALL")
public class ArrayList<E> extends AbstractList<E> implements List<E> {

    /**
     * 存储元素的数组
     */
    private Object[] elements;

    /**
     * 容量为 0
     */
    private static final Object[] EMPTY_ELEMENTS = {};

    /**
     * 默认容量: 10
     */
    private static final int DEFAULT_CAPACITY = 10;

    public ArrayList() {
        this(DEFAULT_CAPACITY);
    }

    public ArrayList(int capacity) {
        if (capacity > 0) {
            this.elements = new Object[capacity];
        } else if (capacity == 0) {
            this.elements = EMPTY_ELEMENTS;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: " + capacity);
        }
    }

    /**
     * 给定索引，返回该元素并强转为 E
     *
     * @param index 指定索引
     * @return E
     */
    private E elementData(int index) {
        return (E) elements[index];
    }

    /**
     * 扩容，保证要具备 capacity 的容量大小
     *
     * @param capacity 容量大小
     */
    private void ensureCapacity(int capacity) {
        // 旧的容量
        int oldCapacity = elements.length;
        // 如果旧的容量大于给定的容量，则不需要扩容
        if (oldCapacity >= capacity) return;

        // 扩容，每次扩容旧容量的 1.5 倍, 位运算效率高, oldCapacity >> 1(右移一位) = oldCapacity/2
        int newCapacity = oldCapacity + (oldCapacity >> 1);

        // 数组拷贝
        Object[] newElements = new Object[newCapacity];
        if (size >= 0)
            System.arraycopy(elements, 0, newElements, 0, size);
        elements = newElements;
    }

    /**
     * 缩容，剩余空间只占总容量的一半时进行缩容
     */
    private void trimCapacity() {
        int oldCapacity = elements.length;
        int newCapacity = oldCapacity >> 1; // 新的容量为原来的一半

        // 剩余空间不足总容量的一半 或 总容量不足默认容量，不缩容
        if (size >= newCapacity || oldCapacity <= DEFAULT_CAPACITY)
            return;

        // 缩容，缩小一半
        Object[] newElements = new Object[newCapacity];
        if (size >= 0)
            System.arraycopy(elements, 0, newElements, 0, size);
        elements = newElements;
    }

    @Override
    public int indexOf(E element) {
        if (element == null) {
            for (int i = 0; i < size; i++) {
                if (elements[i] == null)
                    return i;
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (element.equals(elements[i]))
                    return i;
            }
        }
        return -1;
    }

    @Override
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

    @Override
    public E set(int index, E element) {
        rangeCheck(index);

        E oldElement = elementData(index);
        elements[index] = element;
        return oldElement;
    }

    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        // 确保容量，扩容: new 一个更大的 Array，将引用指向这个 Array
        ensureCapacity(size + 1);

        // 数组右移
        System.arraycopy(elements, index, elements, index + 1, size - index);

        // 添加
        elements[index] = element;
        size++;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);

        E oldElement = elementData(index);
        // 数组左移
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elements, index + 1, elements, index, numMoved);
        elements[--size] = null;

        // 确定是否要缩容
        trimCapacity();
        return oldElement;
    }

    @Override
    public boolean remove(E element) {
        if (element == null) {
            for (int index = 0; index < size; index++)
                if (elements[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (element.equals(elements[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

    /**
     * 没有边界检查且不返回元素的删除方法
     *
     * @param index 索引
     */
    private void fastRemove(int index) {
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elements, index + 1, elements, index, numMoved);
        elements[--size] = null;
    }

    @Override
    public void clean() {
        // 让元素都为 null(数组中的元素可能不是基本类型)，让 GC 回收数组中的对象
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0; // 清空容器

        // 缩容: 如果不为空且容量大于默认容量
        if (elements != null && elements.length > DEFAULT_CAPACITY)
            elements = (E[]) new Object[DEFAULT_CAPACITY];
    }

    @Override
    public void forEach(Consumer<? super E> action) {
        final E[] elements = (E[]) this.elements;
        final int size = this.size;
        for (int i = 0; i < size; i++) {
            action.accept(elements[i]);
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            if (i > 0) sb.append(", ");
            sb.append(elements[i]);
        }
        sb.append("]");
        return sb.toString();
    }

}
